package cn.mayday.algorithms.year2021.month1.动态规划或者贪心;

import java.util.List;

/**
 * 三角形最小路径和 【难度中等】
 * <p>
 * 动态规划经典
 *
 * @author Mayday05
 * @date 2021/5/13 10:29
 */
public class Leetcode120MinimumTotal {

    public static void main(String[] args) {

    }

    // 方法一：动态规划

//    细节
//
//    状态转移方程的边界条件是什么？由于我们已经去除了所有「没有意义」的状态，因此边界条件可以定为：
//
//    f[0][0] = c[0][0]
//
//    即在三角形的顶部时，最小路径和就等于对应位置的元素值。
//    这样一来，我们从 1 开始递增地枚举 i，并在 [0, i]的范围内递增地枚举 j，就可以完成所有状态的计算。



    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] f = new int[n][n]; // 定义记忆数组，其实就是dp[][]


        f[0][0] = triangle.get(0).get(0); // 边界条件初始化

        for (int i = 1; i < n; ++i) { // 循环
            f[i][0] = f[i - 1][0] + triangle.get(i).get(0); // 三角形最左边边界，只有一个来源

            for (int j = 1; j < i; ++j) { // 第二个j开始遍历【注意，j的方位为0-i递增】
                f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle.get(i).get(j); // 状态转换方程
            }

            f[i][i] = f[i - 1][i - 1] + triangle.get(i).get(i); // 三角形最右边边界，只有一个来源
        }


        int minTotal = f[n - 1][0]; // 因为我们要找达到最后一层的最小值，因此就是找dp[N][]一维数组的最大值

        // 找dp[N][]一维数组的最大值
        for (int i = 1; i < n; ++i) {
            minTotal = Math.min(minTotal, f[n - 1][i]);
        }
        return minTotal;
    }

}
